The present invention relates to a data compressing method to be performed with reference to a dictionary which registers a registered data string as correlated with a registration number, to a data restoring method for restoring the compressed data, and an information processing apparatus for compressing the data strings and for restoring the compressed data strings.
Such information processing apparatuses as printers have recently been facing a demand for their increased added value achieved through their supply of bit map fonts and outline fonts in various print character sizes and for high quality to be maintained for any and all print character sizes. In view of these circumstances, data compressing technology, which provides a way of efficient storage of a large amount of information containing these font data, has recently begun to attract much attention in the field of printers and the like.
The publicly known conventional techniques for data compression for storing or transmitting a large amount of information in as small a capacity as possible include the technique for converting data in fixed length bits into a code in a variable length bits, such as the Huffman Code, and a technique for performing a data compression by utilization of an agreement between the data strings which appeared in the past and the data strings to be compressed hereafter, such as the techniques in a patent generally called "the Lempel-Ziv patent" (as disclosed in the Specification for the U.S. Pat. No. 4,464,650) and the techniques in the LZW patent (as disclosed in the Specification for the U.S. Pat. No. 4,558,302).
However, these conventional techniques are data compressing methods performed by using the so-called dynamic dictionary. That is to say, these techniques represent a method for performing an analysis of the object data to be compressed, registering the data in the form of a dictionary structure while checking the frequency of occurrence and the like, and concurrently keep compressing the data with reference to this dictionary. In this case, it is a feature characteristic of such a method that the dictionary undergoes steady changes on a real-time basis. In a data compression with such a dynamic dictionary, there remain as generated products only those data taken as objects and subjected to their data compression, but a restoration of such compressed data requires an examination of the history data as of the time of their data compression and a restoration of the next data through a re-compilation of the dictionary. Therefore, such a conventional technique presents the disadvantage that the data restoring operation must be performed in a serial order starting with the beginning of the compressed data taken up as the objects of the data restoration.
Now, the compression of font data in a printer or the like is performed in such a manner that the compressed font data are stored in a memory device provided either at the printer side or at the host computer side. Then, at the time of a printing operation, the system takes out the compressed font data as necessary from the memory device and forms the print character data by restoring the compressed font data to the ordinary data. Therefore, in case any data compression is to be employed under conditions like these, the requisite is how promptly the system restores the compressed data stored in the memory device and generate the print character data.
Also, another point which becomes important at a time when font data are to be compressed in a printer or the like is to provide the kind of operating freedom that ensures the possibility of putting out the print character data (i.e., letters) in any sequential order. In other words, it is to be required of a printer to make random access to the data stored in a memory device in it and to form print character data at random.
It is considered that such data compressing methods as those disclosed in the Lempel-Ziv patent specification and in the LZW patent specification, which are considered to be capable of attaining a higher ratio of data compression than by any such data compression method as that of the Huffman Code, will form a main current of the data compressing technology to be established from this time onward. In the meanwhile, however, these data compressing techniques operate in a data compressing process to be performed with reference to a dynamic dictionary, and, for this reason, the data restoring process by any of these methods requires an examination of the past data characteristics and the updating of the data, and, consequently, these data compressing methods present the disadvantage that each of them takes time in the restoration of the compressed data.
Further, the data compressing methods disclosed in the Lempel-Ziv patent and the LZW patent require that the compressed data should be restored in a serial order from the beginning of the data when the compressed data are to be restored, and these methods thus present the disadvantage that these methods does not allow the operator to take out only the necessary print character data when only such data are needed.
Furthermore, the data compressing method which is called an incremental decomposition method, which is used in the LZW method, etc., cannot increase the number of data strings one by one, so that the data compressing method presents the disadvantage that it is not capable of attaining any moderate further increase of the data compression ratio, for example, in case the same data strings appear in succession.